package it.uniroma2.tk;

import it.uniroma2.util.tree.Tree;

import java.util.HashMap;
import java.util.Vector;

import edu.berkeley.compbio.jlibsvm.kernel.KernelFunction;

/**
 * @author Lorenzo Dell'Arciprete
 * Naive (unefficient) implementation of the Subpath Tree Kernel between two Tree objects,
 * inspired to the classic Tree Kernel algorithm 
 */
public class SubpathTreeKernel implements KernelFunction<Tree> {

	public static double lambda = 1;
	private static int nodeCount = 0;
	private static HashMap<String,Double> deltaMatrix; 
	private static HashMap<Tree,Integer> nodeIndices; 
	
	public static double value(Tree a, Tree b) {
		deltaMatrix = new HashMap<String,Double>();
		nodeIndices = new HashMap<Tree,Integer>();
		nodeCount = 0;
		double sum = 0;
		for (Tree aa : allNodes(a))
			for (Tree bb : allNodes(b))
				sum += delta(aa,bb);
		return sum;
	}

	private static double delta(Tree a,Tree b) {
		double k = 0;
		if (!nodeIndices.containsKey(a)) {
			nodeIndices.put(a,nodeCount);
			nodeCount++;
		}
		if (!nodeIndices.containsKey(b)) {
			nodeIndices.put(b,nodeCount);
			nodeCount++;
		}
		if (deltaMatrix.containsKey(nodeIndices.get(a) + ":" +nodeIndices.get(b))) {
			return deltaMatrix.get(nodeIndices.get(a) + ":" +nodeIndices.get(b));
		}

		if (a.getRootLabel().equals(b.getRootLabel())) {
			k = 1;
			for (Tree c1 : a.getChildren())
				for (Tree c2 : b.getChildren())
					if (c1.getRootLabel().equals(c2.getRootLabel()))
						k = k + delta(c1,c2);
			k = lambda * k;
		}
		deltaMatrix.put(nodeIndices.get(a) + ":" +nodeIndices.get(b),k);
		return k;
	}
	
	private static Vector<Tree> allNodes(Tree node) {
		Vector<Tree> all = new Vector<Tree>();
		all.add(node);
		for (Tree child : node.getChildren())
			all.addAll(allNodes(child));
		return all;
	}

	public double evaluate(Tree arg0, Tree arg1) {
		return value(arg0, arg1);
	}
	
}
